package demo.practice.stack;

public class Offer30_2 {
    class MinStack {

        private int[] stack;    // 模拟堆栈-数据存放容器
        private int min;    // 存储 当前堆栈 的 最小值
        private int topP;   // 存储 当前堆栈 的 最大下标（栈顶指针）

        /** initialize your data structure here. */
        public MinStack() {
        /*
            此处 申请空间大小 为 40000，原因为：
                各函数的调用总次数不超过 20000 次，
                而 之后的操作，最坏的可能性，就是一直push更小的值
                因此，大小要为 调用次数 的 2倍
                当然，我们也可以实现动态扩缩容，参照list、set的实现
                但是，本题中，我们就来简单实现下
        */
            stack = new int[40000];
            min = Integer.MAX_VALUE;
            topP = -1;
        }

        public void push(int x) {
        /*
            当 push的值 比 最小值 还小 时：
                将最小值入栈，以便之后的pop操作
        */
            if (x <= min) {
                stack[++topP] = min;
                min = x;
            }

            // 将 最新值 入栈
            stack[++topP] = x;
        }

        public void pop() {
        /*
            当 pop的值 等于 最小值 时：
                将 最小值 弹出给 min（照应 push操作）
        */
            if (min == stack[topP]) {
                min = stack[--topP];
            }

            // 将 栈顶指针 “下移”
            topP--;
        }

        public int top() {
            return stack[topP];
        }

        public int min() {
            if (topP >= 0) {
                return min;
            } else {
                return -1;
            }
        }
    }

}
